package com.example.demo.arithmetic.datastructure.linkedlist2;

/**
 * 判断链表是否有环
 */
public class Leetcode142 {
    public static void main(String[] args) {
        ListNode n12 = new ListNode(12, null);
        ListNode n11 = new ListNode(11, n12);
        ListNode n10 = new ListNode(10, n11);
        ListNode n9 = new ListNode(9, n10);
        ListNode n8 = new ListNode(8, n9);
        ListNode n7 = new ListNode(7, n8);
        ListNode n6 = new ListNode(6, n7);
        ListNode n5 = new ListNode(5, n6);
        ListNode n4 = new ListNode(4, n5);
        ListNode n3 = new ListNode(3, n4);
        ListNode n2 = new ListNode(2, n3);
        ListNode n1 = new ListNode(1, n2);
        n12.next = n8;
        System.out.println(new Leetcode142().hasCycle(n1));
        System.out.println(new Leetcode142().checkCycle(n1).val);
    }

    /**
     * 1.龟每次走一步，兔子一次走两步
     * 2.当兔子能走到终点时，不存在环
     * 3.当兔子能追上龟时，必存在环
     *
     * @param head
     * @return
     */
    public boolean hasCycle(ListNode head) {
        // rabbit
        ListNode r = head;
        // tortoise
        ListNode t = head;
        // 当兔子能走到终点时，不存在环
        while (r != null && r.next != null) {
            t = t.next;
            r = r.next.next;
            if (t == r) {
                return true;
            }
        }
        return false;

    }

    /**
     * 从他们第一次相遇开始，鬼回到起点，兔子保持原位不变
     * 龟和兔子一次都走一步
     * 当再次相遇时，地点就是环的入口
     *
     * @param head
     * @return
     */
    public ListNode checkCycle(ListNode head) {
        // rabbit
        ListNode r = head;
        // tortoise
        ListNode t = head;
        // 当兔子能走到终点时，不存在环
        while (r != null && r.next != null) {
            t = t.next;
            r = r.next.next;
            if (t == r) {
                t = head;
                while (true) {
                    if (t == r) {
                        return r;
                    }
                    t = t.next;
                    r = r.next;
                }
            }
        }
        return null;
    }
}
